package org.example;

public class Test2 {
    //leetcode 112 路径总和 https://leetcode.cn/problems/path-sum/description/
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        return traversal(root,0,targetSum);
    }

    public boolean traversal(TreeNode root,int sum,int targetSum) {
        if (root == null) return false;
        sum += root.val;
        if (root.left == null && root.right == null) {
            if (sum == targetSum) return true;
        }
        boolean leftRet = traversal(root.left,sum,targetSum);
        if (leftRet) return true;
        return traversal(root.right,sum,targetSum);
    }

    /**
     * 回溯
     */
    int sum;
    public boolean hasPathSum2(TreeNode root, int targetSum) {
        if (root == null) return false;
        return traversal(root,targetSum);
    }

    public boolean traversal(TreeNode root,int targetSum) {
        if (root == null) return false;
        sum += root.val;
        if (root.left == null && root.right == null) {
            if (sum == targetSum) return true;
        }
        boolean leftRet = traversal(root.left,targetSum);
        if (leftRet) return true;
        boolean rightRet = traversal(root.right,targetSum);
        sum -= root.val;
        return rightRet;
    }
}
